package main

// https://leetcode.cn/problems/powx-n/
// 快速幂 + 递归
// log(n) log(n)
func myPow(x float64, n int) float64 {
	var N int64 = int64(n)
	if N >= 0 {
		return quickMul(x, N)
	} else {
		return 1.0 / quickMul(x, -N)
	}
}

func quickMul(x float64, N int64) float64 {
	if N == 0 {
		return 1.0
	}
	y := quickMul(x, N/2)
	if N%2 == 0 {
		return y * y
	} else {
		return y * y * x
	}
}
